package chapter01;

import java.util.Arrays;

public class Multiply {
    /** 模拟竖式乘法
     *            下标 4 3 2 1 0 <-
     *               str1  9 9 9
     *               str2  x 9 9
     *                   --------
     *                  8 9 9 1
     *                8 9 9 1
     *               ------------
     *            res 9 8 9 0 1
     *           下标 4 3 2 1 0 <-
     *   即999*9+(999*9)<<1
     *  为了方便低位向高位进位计算 将字符串逆序存储在数组中 [低位->高位]  "132"->"231"
     *  计算结果也是逆序存储 只需将结果从数组逆序输出[低位<-高位]
     *  str1[i]*str2[j]得到的结果应存放在res[i+j]位置
     *  因为有进位计算 我们先设置一个进位pre 初始化pre=0
     *  观察计算过程    [i+j]=上一次进位值+[i]*[j]+之前计算[i+j]已存在值
     *  res[i+j]=(res[i+j]+str[i]*str2[j]+pre)%10
     *  pre=(res[i+j]+str[i]*str2[j]+pre)/10
     *  模拟之后可以观察到在一轮循环结束后 最后一次的进位计算没有考虑进去 因此需要特别判断一轮循环结束后的进位情况
     *  999*9='8'991 按照思路一轮循环结束时'8'没有进行进位计算得到991 需要在循环外单独判断是否需要进位计算
     */
    public String multiply(String num1, String num2) {
        if(num2.length()==1&&num2.charAt(0)=='0'||num1.length()==1&&num1.charAt(0)=='0'){
            return "0";
        }
        char[] str1=new char[num1.length()];
        char[] str2=new char[num2.length()];
        char[] res=new char[str1.length+str2.length];
        praseChar(str1,num1);
        praseChar(str2,num2);
        int index=0;
        int pre=0;
        Arrays.fill(res,'0');
        int i,j;
        int temp;
        for(i=0;i<str1.length;i++){
            for(j=0;j<str2.length;j++){
                temp=res[i+j]-'0'+pre+(str1[i]-'0')*(str2[j]-'0');
                pre=temp/10;
                res[i+j]=(char)(temp%10+'0');
                if(index<i+j){
                    index=i+j;
                }
            }
            if(pre!=0){
                res[i+j]=(char)(pre+res[i+j]-'0'+'0');
                pre=0;
                index=Math.max(index,i+j);
            }
        }
        StringBuilder strBuilder=new StringBuilder();
        for(i=index;i>=0;i--){
            strBuilder.append(res[i]);
        }
        return strBuilder.toString();
    }

    public void praseChar(char[] str,String s){
        int length=s.length();
        for(int i=0,j=length-1;i<length;i++,j--){
            str[i]=s.charAt(j);
        }
    }

}
